☝ La réciproque est fausse - Remarque

Supposons que $n^{p-1}\equiv 1[p]$ pour tout $n\in \mathbb{Z}$ tel que $p$ est premier avec  $n$ : peut-on en déduire que $p$ est premier ? Cela signifierait que la réciproque du petit théorème de Fermat est vraie... mais ce n'est pas le cas !

Exemple

On considère le nombre $p=561=3\times 11\times 17$  qui n'est clairement pas un nombre premier !

Soit $n\in \mathbb{Z}$ un entier qui est premier avec  $561$ . Par conséquent, $n$ n'est divisible ni par $3$ , ni par $11$ , ni par $17$  (sinon il ne serait pas premier avec  $561$  !).

Comme $3$ , $11$ et $17$ sont premiers, d'après le petit théorème de Fermat (forme forte), on a :

• $n^2\equiv 1[3]$ , donc $(n^2{)}^{280}\equiv 1^{280}[3]$ , c'est-à-dire $n^{560}\equiv 1[3]$ ;
• $n^{10}\equiv 1[11]$ , donc $(n^{10}{)}^{56}\equiv 1^{56}[11]$ , c'est-à-dire $n^{560}\equiv 1[11]$ ;
• $n^{16}\equiv 1[17]$ , donc $(n^{16}{)}^{35}\equiv 1^{35}[17]$ , c'est-à-dire $n^{560}\equiv 1[17]$ .

On en déduit que $n^{560}-1$ est divisible par $3$ et par $11$ , qui sont premiers entre eux, donc, d'après le corollaire du théorème de Gauss, $n^{560}-1$ est divisible par $3\times 11=33$ .

Ensuite, $n^{560}-1$ est divisible par $33$ et par $17$ , qui sont premiers entre eux, donc, d'après le corollaire du théorème de Gauss, $n^{560}-1$ est divisible par $33\times 17=561$ .

On a donc $n^{560}\equiv 1[561]$ , avec $561$ qui ne divise pas $n$ , et pourtant, $561$ n'est pas premier.